package br.edu.unifei.mestrado.unfold;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import br.edu.unifei.mestrado.commons.graph.GraphWrapper;
import br.edu.unifei.mestrado.commons.graph.NodeWrapper;
import br.edu.unifei.mestrado.commons.graph.RelationshipWrapper;
import br.edu.unifei.mestrado.commons.mn.GN;
import br.edu.unifei.mestrado.commons.partition.AbstractPartition;
import br.edu.unifei.mestrado.commons.partition.AbstractPartitionIndex;
import br.edu.unifei.mestrado.commons.partition.BestPartition;
import br.edu.unifei.mestrado.commons.view.ViewListener;
import br.edu.unifei.mestrado.unfold.mn.CoarseHelper;

public abstract class Unfold implements ViewListener {

	private Logger logger = LoggerFactory.getLogger(this.getClass());

	private int m = -1;

	private int doisM = -1;

	private PartitionUnfold partition;

	public abstract GraphWrapper createNewGraph(int level);

	public abstract GraphWrapper getGraph();

	public abstract AbstractPartitionIndex getPartitionIndex(int k);

	public void execute(int numberOfSets) {
		GraphWrapper currentGraph = getGraph();
		try {
			currentGraph.beginTransaction();
			currentGraph.readGraph();
			currentGraph.endTransaction();
		} finally {
			currentGraph.finish();
		}
		int k = currentGraph.getSizeNodes();

		int level = GraphWrapper.FIRST_lEVEL;

		int setSize = Integer.MAX_VALUE;

		GN gn = new GN();
		gn.setGraph(currentGraph, partition, level);
		prepare();
		initView(currentGraph);

		while (setSize > numberOfSets) {
			partition = new PartitionUnfold(level, k, getPartitionIndex(k));

			phaseOne(currentGraph);
			GraphWrapper newGraph = phaseTwo(level, currentGraph);

			if (logger.isDebugEnabled()) {
				newGraph.printGraph();
			}
			setSize = 0;

			// UTIL: conta a quantidade de particoes que possuem nodes
			for (int setId = 0; setId < partition.getK(); setId++) {
				Iterable<NodeWrapper> nodes = partition.getNodesFrom(setId);
				if (nodes.iterator().hasNext()) {
					setSize++;
					logger.info("Nodes of set: " + setId + " {} ", nodes);
				}
			}
			logger.info("Final Cut Weight level " + level + " : " + partition.getCutWeight());
			updateView(newGraph, level, "", partition.getCutWeight());

			currentGraph = newGraph;
			k = currentGraph.getSizeNodes();
			level++;
			gn.setGraph(currentGraph, partition, level);
		}
	}

	/**
	 * Executa a expanção do grafo. <br>
	 * <br>
	 * 1) Repassa o particionamento de volta para o grafo mais fino. <br>
	 * 2) Melhora o particionamento usando o refinamento.
	 */
	protected BestPartition uncoarseGraph(GN gn, int level, BestPartition bestPartM_1) {

		GraphWrapper grafoM_1 = gn.getGraph(level);
		GraphWrapper grafoM = gn.getGraph(level + 1);

		gn.projectPartitionBack(grafoM_1, grafoM);

		// so para mostrar na tela
		updateView(grafoM, level, "NO_IT", gn.getPartitionOfLevel(level).getCutWeight());
		updateViewCoarsed(grafoM_1, level - 1, "NO_IT", gn.getPartitionOfLevel(level).getCutWeight());

		logger.info("Partition of level " + level);
		AbstractPartition partition = gn.getPartitionOfLevel(level);
		BestPartition part = partition.createBestPartition();
		part.printSets();
		return part;
	}

	private void prepare() {
		for (RelationshipWrapper edge : getGraph().getAllEdges()) {
			m += edge.getWeight();
		}
		doisM = m * 2;
		logger.info("Peso total de arestas: {}", m);
	}

	private void phaseOne(GraphWrapper graph) {
		boolean hadImprovements = false;
		int greaterWeight = assignInitialConnunities(graph);
		int weightAllowed = (int) (greaterWeight / 2);
		if(weightAllowed == 0) {
			weightAllowed = 1;
		}
		repaint();
		partition.print();

		while (!hadImprovements) {

			for (NodeWrapper node : graph.getAllNodes()) {

				// UTIL: não deixa o node se juntar em outras communities, para não aumentar muito o peso
				// final da community
				if (node.getWeight() <= weightAllowed) {

					Integer bestCommunity = evaluateModularityGain(node);
					if (bestCommunity != null) {
						logger.info("Node " + node.getId() + " indo do set " + node.getPartition()
								+ " para o set " + bestCommunity);
						joinNodeToCommunity(node, bestCommunity);
						node.lock();
						hadImprovements = true;

						repaint();
					} else {
						logger.info("Node {} não possui melhor vizinhanca.", node);
					}
				}
			}
		}
	}

	private GraphWrapper phaseTwo(int level, GraphWrapper graph) {
		GraphWrapper newGraph = createNewGraph(level++);

		CoarseHelper coarser = new CoarseHelper(partition);
		coarser.coarseOneLevel(level, graph, newGraph);

		return newGraph;
	}

	/**
	 * Atribui os clusters iniciais, e mantém o valor do node com maior peso
	 * 
	 * @param graph
	 * @return
	 */
	private int assignInitialConnunities(GraphWrapper graph) {
		Integer partitionNumber = 0;
		int greaterWeight = -1;
		for (NodeWrapper node : graph.getAllNodes()) {
			node.setPartition(partitionNumber);

			// atualiza os sets com o novo nó e aresta
			partition.addNodeToSet(partitionNumber, node);

			updateInitialEdgeCut(node, partitionNumber);
			partitionNumber++;

			int weight = node.getWeight();
			if (weight > greaterWeight) {
				greaterWeight = weight;
			}
		}
		return greaterWeight;
	}

	private Integer evaluateModularityGain(NodeWrapper node) {
		// TODO: precisa de alguma forma considerar o peso do node, pois existe a tendencia do node inchar.
		int myPartition = node.getPartition();
		int ki = 0;

		// mantém os nodes de cada partição vizinha
		Map<Integer, List<RelationshipWrapper>> linksFromIToC = new HashMap<Integer, List<RelationshipWrapper>>();

		for (RelationshipWrapper edge : node.getRelationships()) {
			NodeWrapper other = edge.getOtherNode(node);
			if (!other.isLocked()) {
				if (other.getPartition() == myPartition) {
					ki += edge.getWeight(); // ki
				} else {
					List<RelationshipWrapper> list = linksFromIToC.get(other.getPartition());
					if (list == null) {
						list = new ArrayList<RelationshipWrapper>();
						linksFromIToC.put(other.getPartition(), list);
					}
					list.add(edge);
				}
			}
		}

		// contabiliza o kiin
		Map<Integer, Integer> sumOfWeightsFromIToC = processKiin(linksFromIToC);

		Integer bestPartition = findBestPartition(ki, sumOfWeightsFromIToC);
		return bestPartition;
	}

	/**
	 * Encontra a melhor partição, com maior deltaQ, baseado em ki e na soma dos pesos de i para C.
	 * 
	 * @param ki
	 * @param sumOfWeightsFromIToC
	 * @return
	 */
	private Integer findBestPartition(int ki, Map<Integer, Integer> sumOfWeightsFromIToC) {
		Integer bestPartition = null;
		// loop para descobir qual a melhor partição para o nó ir
		double bestPartitionDeltaQ = 0D;

		for (Integer partition : sumOfWeightsFromIToC.keySet()) {

			int kiin = sumOfWeightsFromIToC.get(partition);// pega o valor de kiin

			// contabiliza o Stot
			int Stot = this.partition.getCutWeightBySetId(partition);
			// Iterable<RelationshipWrapper> edges = this.partition.getEdgesCutFromSet(partition);
			// for (RelationshipWrapper edge : edges) {
			// Stot += edge.getWeight();
			// }

			int Sin = processSin(partition);

			double deltaQ = calculateDeltaQ(Sin, Stot, ki, kiin);
			if (deltaQ > bestPartitionDeltaQ) {
				bestPartitionDeltaQ = deltaQ;
				bestPartition = partition;
			}
		}
		return bestPartition;
	}

	/**
	 * Retorna o valor do ganho em modularidade, de acordo com a formula.
	 * 
	 * @param Sin
	 * @param Stot
	 * @param ki
	 * @param kiin
	 * @return
	 */
	private double calculateDeltaQ(int Sin, int Stot, int ki, int kiin) {
		double deltaQ = ((Sin + kiin) / doisM - ((Stot + ki) ^ 2) / doisM)
				- ((Sin / doisM) - ((Stot / doisM) ^ 2) - (ki / doisM) ^ 2);
		return deltaQ;
	}

	/**
	 * Calcula a soma dos pesos das arestas dento de C.
	 * 
	 * @param partition
	 * @return
	 */
	private int processSin(int partition) {
		int Sin = 0;
		Iterable<NodeWrapper> nodes = this.partition.getNodesFrom(partition);
		if (nodes.iterator().hasNext()) {

			// map que armazena o id da aresta e seu peso.
			// faz isso para não contar arestas 2 vezes
			Map<Long, Integer> mapEdgesWeight = new HashMap<Long, Integer>();
			for (NodeWrapper nodeTmp : nodes) {
				int nodePart = nodeTmp.getPartition();
				for (RelationshipWrapper edge : nodeTmp.getRelationships()) {
					NodeWrapper other = edge.getOtherNode(nodeTmp);
					if (other.getPartition() == nodePart) {// nós na mesma partição, então, é aresta interna.
						mapEdgesWeight.put(edge.getId(), edge.getWeight());
					}
				}
			}
			// soma o peso das arestas dentro de C
			for (Integer weight : mapEdgesWeight.values()) {
				Sin += weight;
			}
		}
		return Sin;
	}

	/**
	 * Calcula a soma das arestas de i para os nodes em C, a partir das arestas que saem de i e vão para C.
	 * 
	 * @param linksFromIToC
	 * @return Um map com: a partição C | valor da soma kiin
	 */
	private Map<Integer, Integer> processKiin(Map<Integer, List<RelationshipWrapper>> linksFromIToC) {

		// partition | weights from I to partition C
		Map<Integer, Integer> sumOfWeightsFromIToC = new HashMap<Integer, Integer>();

		for (Integer partition : linksFromIToC.keySet()) {
			List<RelationshipWrapper> edges = linksFromIToC.get(partition);
			int kiin = 0;
			for (RelationshipWrapper edgesToJ : edges) {
				kiin += edgesToJ.getWeight();
			}
			sumOfWeightsFromIToC.put(partition, kiin);
		}
		return sumOfWeightsFromIToC;
	}

	/**
	 * Atualiza as arestas do corte inicial para o newSet
	 * 
	 * @param node
	 * @param bestCommunity
	 * @param newSet
	 */
	private void updateInitialEdgeCut(NodeWrapper node, int bestCommunity) {
		for (RelationshipWrapper edge : node.getRelationships()) {
			// adiciona direto a aresta no corte do newSet.
			partition.addEdgeToSet(bestCommunity, edge);
		}
	}

	/**
	 * Insere o node na bestCommunity e remove do oldSet.
	 * 
	 * @param node
	 * @param bestCommunity
	 */
	private void joinNodeToCommunity(NodeWrapper node, Integer bestCommunity) {
		int newPartition = bestCommunity;
		int oldPartition = node.getPartition();
		node.setPartition(bestCommunity);

		partition.addNodeToSet(newPartition, node);
		partition.removeNodeFromSet(oldPartition, node);

		updateEdgeCut(node, bestCommunity, oldPartition);

		partition.print();
	}

	/**
	 * Atualiza as arestas do corte de set e oldSet.
	 * 
	 * @param node
	 * @param newSetId
	 * @param newSet
	 * @param oldSet
	 */
	private void updateEdgeCut(NodeWrapper node, int newSetId, int oldSetId) {
		for (RelationshipWrapper edge : node.getRelationships()) {
			NodeWrapper other = edge.getOtherNode(node);
			if (other.getPartition() == newSetId) {// quando a outra ponta esta na particao nova
				// se a aresta estiver no corte, ela eh removida dos dois sets.
				// remove a aresta, pois ela nao esta mais no corte.

				partition.removeEdgeFromSet(newSetId, edge);
				partition.removeEdgeFromSet(oldSetId, edge);
			} else if (other.getPartition() == oldSetId) {// quando a outra ponta esta na particao old

				partition.addEdgeToSet(newSetId, edge);
				partition.addEdgeToSet(oldSetId, edge);

			} else {// quando a outra ponta esta em outra particao (nem nova nem old)
				// se a aresta não tiver no corte, ela deve entrar no corte somente para o set novo
				partition.addEdgeToSet(newSetId, edge);

				// e somente remove do corte do oldSet, pois ela ainda deve continuar no corte geral
				partition.removeEdgeOnlyFromSet(oldSetId, edge);
			}
		}
	}
}
